#!/usr/bin/python3
# -*- coding: utf-8 -*-
# create by 火苗999℃
import random
from draw_maze import *
from maze_def import *
from maze import *
#
# Randomized depth-first search
# Recursive implementation
#1。Choose the initial cell, mark it as visited and push it to the stack
#2。While the stack is not empty
#   1。Pop a cell from the stack and make it a current cell
#   2。If the current cell has any neighbours which have not been visited
#       1。Push the current cell to the stack
#       2。Choose one of the unvisited neighbours
#       3。Remove the wall between the current cell and the chosen cell
#       4。Mark the chosen cell as visited and push it to the stack
#随机深度优先搜索
#递归实现
#1。选择初始单元格，将其标记为已访问，并将其压入堆栈
#2。而堆栈不是空的
#   1。从堆栈中弹出一个单元格并使其成为当前单元格
#   2。如果当前单元有任何未被访问的邻居
#       1。将当前单元格压入堆栈
#       2。选择一个未被拜访的邻居
#       3。移除当前单元格和所选单元格之间的墙
#       4。将选中的单元格标记为已访问的，并将其压入堆栈
# 多层迷宫 


# 标记格子已经访问
def visit_cell(maze_map, x, y, z, cols, rows):
    if maze_map[x][y][z] == CELL_NO_VISIT: 
        maze_map[x][y][z] = CELL_VISIT # 标记访问
    grids = []
    minx = x
    while True:
        if minx > 1 and maze_map[minx-1][y][z] == CELL_NO_VISIT:
            minx -=1
        else:
            break
    maxx = x
    while True:
        if maxx < cols - 2 and maze_map[maxx+1][y][z] == CELL_NO_VISIT:
            maxx+=1
        else:
            break    
    miny=y
    while True:
        if miny > 1 and maze_map[x][miny-1][z] == CELL_NO_VISIT:
            miny -=1
        else:
            break
    maxy=y
    while True:
        if maxy < rows - 2 and maze_map[x][maxy+1][z] == CELL_NO_VISIT:
            maxy +=1
        else:
            break
    for xi in range(minx, maxx+1):
        for yi in range(miny, maxy+1):
            if  maze_map[xi][yi][z] == CELL_NO_VISIT: 
                maze_map[xi][yi][z] = CELL_VISIT
            grids.append((xi,yi,z))
    return grids


def depth_maze_demo(levels, rows, cols):
    if 0 == levels % 2:
        levels+=1
    if 0 == rows % 2:
        rows+=1
    if 0 == cols % 2:
        cols+=1
    # 初始化全为墙
    maze_map = maze_init_draw2(levels,rows,cols, 5, 3, 5)
    # 设置起点
    nowx=1
    nowy=1
    nowz=0
    # 起点加入记录
    history = []
    grids = visit_cell(maze_map, nowx, nowy, nowz, cols, rows)
    history.extend(grids)
    # 1。选择初始单元格，将其标记为已访问，并将其压入堆栈
    # 2。堆栈不是空的
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                return

        if history:
            if maze_map[nowx][nowy][nowz] == CELL_NO_VISIT:
                grids = visit_cell(maze_map, nowx, nowy, nowz, cols, rows)
                history.extend(grids)

            check = []
            # 可以移动到的位置
            if nowx > 1:
                if maze_map[nowx-2][nowy][nowz] == CELL_NO_VISIT:
                    check.append('L')  
                elif maze_map[nowx-1][nowy][nowz] == WALL_NO_VISIT:
                    # 标记墙已访问(演示用)
                    maze_map[nowx-1][nowy][nowz] = WALL_VISIT
            if nowy > 1 :
                if maze_map[nowx][nowy-2][nowz] == CELL_NO_VISIT:
                    check.append('F')
                elif maze_map[nowx][nowy-1][nowz] == WALL_NO_VISIT:
                    # 标记墙已访问(演示用)
                    maze_map[nowx][nowy-1][nowz] = WALL_VISIT
            if nowx < cols-2:
                if maze_map[nowx+2][nowy][nowz] == CELL_NO_VISIT:
                    check.append('R')
                elif maze_map[nowx+1][nowy][nowz] == WALL_NO_VISIT:
                    # 标记墙已访问(演示用)
                    maze_map[nowx+1][nowy][nowz] = WALL_VISIT
            if nowy < rows-2:
                if maze_map[nowx][nowy+2][nowz] == CELL_NO_VISIT:
                    check.append('B')    
                elif maze_map[nowx][nowy+1][nowz] == WALL_NO_VISIT:
                    maze_map[nowx][nowy+1][nowz] = WALL_VISIT
            if nowz < levels-2:
                if  maze_map[nowx][nowy][nowz+2] == CELL_NO_VISIT:
                    check.append('U') 
                elif maze_map[nowx][nowy][nowz+1] == WALL_NO_VISIT:
                    maze_map[nowx][nowy][nowz+1] = WALL_VISIT
            if nowz > 1:
                if maze_map[nowx][nowy][nowz-2] == CELL_NO_VISIT:
                    check.append('D')   
                elif maze_map[nowx][nowy][nowz-1] == WALL_NO_VISIT:
                    maze_map[nowx][nowy][nowz-1] = WALL_VISIT                 
            # 如果当前单元有任何未被访问的邻居
            if len(check): 
                # 选择一个未被拜访的邻居
                # 移除当前单元格和所选单元格之间的墙
                # 将选中的单元格标记为已访问的，并将其压入堆栈
                # 随机选择邻居
                move_direction = random.choice(check)
                # 打通墙壁
                if move_direction == 'L':
                    maze_map[nowx-1][nowy][nowz] = NOWALL # 打通墙
                    nowx=nowx-2
                if move_direction == 'F':
                    maze_map[nowx][nowy-1][nowz] = NOWALL # 打通墙
                    nowy=nowy-2
                if move_direction == 'R':
                    maze_map[nowx+1][nowy][nowz] = NOWALL # 打通墙
                    nowx=nowx+2
                if move_direction == 'B':
                    maze_map[nowx][nowy+1][nowz] = NOWALL # 打通墙
                    nowy=nowy+2
                if move_direction == 'U':
                    maze_map[nowx][nowy][nowz+1] = NOWALL # 打通墙
                    if maze_map[nowx][nowy][nowz] == STAIRS_D:
                        maze_map[nowx][nowy][nowz] = STAIRS_UD # 标记为上下楼梯
                    else:
                        maze_map[nowx][nowy][nowz] = STAIRS_U # 标记为向上楼梯
                    if maze_map[nowx][nowy][nowz+2] == STAIRS_U:
                        maze_map[nowx][nowy][nowz+2] = STAIRS_UD # 标记为上下楼梯
                    else:
                        maze_map[nowx][nowy][nowz+2] = STAIRS_D # 标记为向下楼梯
                    nowz=nowz+2
                if move_direction == 'D':
                    maze_map[nowx][nowy][nowz-1] = NOWALL # 打通墙
                    if maze_map[nowx][nowy][nowz] == STAIRS_U:
                        maze_map[nowx][nowy][nowz] = STAIRS_UD # 标记为上下楼梯
                    else:
                        maze_map[nowx][nowy][nowz] = STAIRS_D # 标记为向下楼梯
                    if maze_map[nowx][nowy][nowz-2] == STAIRS_D:
                        maze_map[nowx][nowy][nowz-2] = STAIRS_UD # 标记为上下楼梯
                    else:
                        maze_map[nowx][nowy][nowz-2] = STAIRS_U # 标记为向上楼梯
                    nowz=nowz-2
                # 将选中的单元格标记为已访问的，并将其压入堆栈
                grids = visit_cell(maze_map, nowx, nowy, nowz, cols, rows)
                history.extend(grids)
            else: 
                #从堆栈中弹出一个单元格并使其成为当前单元格
                nowx, nowy, nowz = history.pop()
        # 
        draw_maze(maze_map, levels, rows, cols, (nowx,nowy,nowz), not history)
        
        time_passed = clock.tick(200)

        pygame.display.update()
    return 


# main
if __name__ == "__main__":
    '''main'''
    depth_maze_demo(3, 15, 21)
